
/*
Author: jfwang213
*/


/*
this program is based on the paper of Esko Ukkonen
on-line construction of suffix trees
*/

#include "suffix_tree.h"
#include "constants.h"
#include "stdlib.h"
#include "string.h"

#define OO 1000000000
#define GET_CHAR_INDEX(X) (X-'a')

void print_one_node(FILE* output_file,suffix_tree *tree,suffix_tree_node *node,int before_gap);


suffix_tree* init_suffix_tree()
{
	int i;
	suffix_tree_node* root = (suffix_tree_node*)malloc(sizeof(suffix_tree_node));
	suffix_tree *tree = (suffix_tree*)malloc(sizeof(suffix_tree));
	//init tree
	tree->root = root;
	tree->str_content = NULL;
	//init root
	for (i = 0;i<CHAR_SET_NUM;i++)
	{
		root->childs[i] = NULL;
	}
	root->beg = 0;
	root->end = -1;
	root->suffix_link = NULL;

	return tree;
}

char test_and_split(suffix_tree *tree,suffix_tree_node *node,int s,int e,int to_insert,suffix_tree_node **expli_node)
{
	char to_insert_char = tree->str_content[to_insert];
	*expli_node = node;
	if (NULL == node)
	{
		//end node
		return TRUE;
	}
	if (e<s)
	{
		if (NULL != node->childs[GET_CHAR_INDEX(to_insert_char)])
		{
			return TRUE;
		}
		else
		{
			return FALSE;
		}
	}
	else
	{
		char s_char = tree->str_content[s];
		suffix_tree_node *next = node->childs[GET_CHAR_INDEX(s_char)];
		int insert_addr = e-s+next->beg+1;
		if (tree->str_content[insert_addr] == to_insert_char)
		{
			return TRUE;
		}
		else
		{
			//split
			suffix_tree_node *split_node = node->childs[GET_CHAR_INDEX(s_char)];
			int split_addr = split_node->beg + e-s + 1;
			char split_char = tree->str_content[split_addr];
			suffix_tree_node *new_node = (suffix_tree_node*)malloc(sizeof(suffix_tree_node));
			memcpy(new_node->childs,split_node->childs,sizeof(new_node->childs));
			memset(split_node->childs,0,sizeof(new_node->childs));
			split_node->childs[GET_CHAR_INDEX(split_char)] = new_node;
			new_node->beg = split_addr;
			new_node->end = split_node->end;
			split_node->end = split_addr-1;
			*expli_node = split_node;
			return FALSE;
		}
	}
}

int canonize(suffix_tree *tree,suffix_tree_node **start_node,int k,int p)
{
	if (NULL == *start_node && (k<=p))
	{
		k++;
		*start_node = tree->root;
	}
	if (k>p)
	{
		return k;
	}
	else
	{
		char first_char = tree->str_content[k];
		suffix_tree_node *to_find_node = (*start_node)->childs[GET_CHAR_INDEX(first_char)];
		while (k<=p)
		{
			if ((to_find_node->end-to_find_node->beg)>(p-k))
			{
				return k;
			}
			else
			{
				k+=to_find_node->end-to_find_node->beg + 1;
				first_char = tree->str_content[k];
				*start_node = to_find_node;
				to_find_node = to_find_node->childs[GET_CHAR_INDEX(first_char)];
			}
		}
		return k;
	}
}

int update(suffix_tree *tree,suffix_tree_node *active_node,int k,int i,suffix_tree_node **end_node)
{
	suffix_tree_node *oldr = tree->root;
	suffix_tree_node *branch_node;
	char end = FALSE;
	char insert_char = tree->str_content[i];
	end = test_and_split(tree,active_node,k,i-1,i,&branch_node);
	while (!end)
	{
		suffix_tree_node *new_node = (suffix_tree_node*)malloc(sizeof(suffix_tree_node));
		branch_node->childs[GET_CHAR_INDEX(insert_char)] = new_node;
		new_node->beg = i;
		new_node->end = OO;
		memset(new_node->childs,0,sizeof(new_node->childs));
		if (oldr != tree->root)
		{
			oldr->suffix_link = branch_node;
		}
		oldr = branch_node;
		active_node = active_node->suffix_link;
		k = canonize(tree,&active_node,k,i-1);
		end = test_and_split(tree,active_node,k,i-1,i,&branch_node);
	}
	if (oldr != tree->root)
	{
		oldr->suffix_link = active_node;
	}
	*end_node = active_node;
	return k;
}

void build_suffix_tree(suffix_tree *tree,char *content)
{
	suffix_tree_node *active_node = tree->root;
	suffix_tree_node *end_node = NULL;
	char end = 0;
	int i;
	int s_addr = 0;
	int len = strlen(content)+1;
	tree->str_content = (char*)malloc(len);
	memcpy(tree->str_content,content,len);
	for (i = 0;tree->str_content[i]!=0;i++)
	{
		s_addr = update(tree,active_node,s_addr,i,&active_node);
		s_addr = canonize(tree,&active_node,s_addr,i);
	}
}

void print_suffix_tree(FILE* output_file,suffix_tree *tree)
{
	int i = 0;
	suffix_tree_node *root = tree->root;
	fprintf(output_file,"root\n");
	for (i = 0;i<CHAR_SET_NUM;i++)
	{
		if (NULL != root->childs[i])
		{
			print_one_node(output_file,tree,root->childs[i],4);
		}
		
	}
}

void print_one_node(FILE* output_file,suffix_tree *tree,suffix_tree_node *node,int before_gap)
{
	int i = 0;
	for (i = 0;i<before_gap;i++)
	{
		fprintf(output_file," ");
	}
	for (i = node->beg;i<=node->end && 0 != tree->str_content[i];i++)
	{
		fprintf(output_file,"%c",tree->str_content[i]);
	}
	fprintf(output_file,"\n");
	before_gap += i-node->beg;
	for (i = 0;i<CHAR_SET_NUM;i++)
	{
		if (NULL != node->childs[i])
		{
			print_one_node(output_file,tree,node->childs[i],before_gap);
		}
	}
}


